package cc.magicjson.example.demo.collection;

import java.util.HashMap;
import java.util.Map;

// 定义一个二叉树节点类 ThreeNode
class ThreeNode {
    int val;      // 节点的值
    ThreeNode left; // 指向左子节点的引用
    ThreeNode right; // 指向右子节点的引用

    // 构造函数，初始化节点的值
    ThreeNode(int x) {
        val = x;
    }
}

// 定义一个解决方案类，包含构建二叉树和打印树的逻辑
class ThreeNodeBuilderSimulation {
    // 使用哈希表存储中序遍历中的值与索引的映射，以便快速检索
    private final Map<Integer, Integer> inOrderMap = new HashMap<>();

    // 根据前序遍历和中序遍历的结果构建二叉树
    public ThreeNode buildTree(int[] preorder, int[] inorder) {
        // 初始化中序遍历的索引映射
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        // 调用递归辅助方法来构建树
        return buildTreeHelper(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    // 递归辅助方法，根据前序遍历和中序遍历的子数组构建子树
    private ThreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {
        // 递归终止条件：当前子数组为空
        if (preStart > preEnd || inStart > inEnd) return null;

        // 前序遍历的第一个元素是当前子树的根节点
        ThreeNode root = new ThreeNode(preorder[preStart]);
        // 获取当前根节点在中序遍历中的索引
        int inRoot = inOrderMap.get(root.val);
        // 计算左子树中的节点数量
        int numsLeft = inRoot - inStart;

        // 递归构建左子树和右子树
        root.left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft, inStart, inRoot - 1);
        root.right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd);

        // 返回构建好的子树的根节点
        return root;
    }

    // 递归方法，按照前序遍历的顺序打印二叉树的节点值
    public void printTree(ThreeNode root) {
        if (root != null) {
            System.out.print(root.val + " "); // 访问根节点
            printTree(root.left);            // 递归访问左子树
            printTree(root.right);           // 递归访问右子树
        }
    }

    // 主方法，用于测试构建二叉树和打印树的功能
    public static void main(String[] args) {
        ThreeNodeBuilderSimulation sol = new ThreeNodeBuilderSimulation();
        // 定义前序遍历和中序遍历的数组
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        // 构建二叉树
        ThreeNode root = sol.buildTree(preorder, inorder);
        // 打印二叉树，按照前序遍历的顺序
        sol.printTree(root); // 预期输出：3 9 20 15 7
    }
}